package com.huangyi;

public class Main {
    public static void main(String[] args) {
        //岛屿的最大面积
        class Solution {
            int m, n;
            boolean[][] vis;
            int[] dx = {0, 0, 1, -1};
            int[] dy = {1, -1, 0, 0};
            int cur;  // 当前岛屿面积

            public int maxAreaOfIsland(int[][] grid) {
                m = grid.length;
                if (m == 0) return 0;
                n = grid[0].length;
                vis = new boolean[m][n];

                int maxArea = 0;
                for (int i = 0; i < m; i++) {
                    for (int j = 0; j < n; j++) {
                        if (grid[i][j] == 1 && !vis[i][j]) {
                            cur = 0;  // 重置计数器
                            int area = dfs(grid, i, j);
                            maxArea = Math.max(maxArea, area);
                        }
                    }
                }
                return maxArea;
            }

            private int dfs(int[][] grid, int x, int y) {
                vis[x][y] = true;
                cur++;  // 统计当前节点

                // 四个方向递归
                for (int i = 0; i < 4; i++) {
                    int nx = x + dx[i];
                    int ny = y + dy[i];
                    if (nx >= 0 && nx < m && ny >= 0 && ny < n
                            && grid[nx][ny] == 1 && !vis[nx][ny]) {
                        vis[nx][ny] = true;  // 提前标记
                        dfs(grid, nx, ny);
                    }
                }
                return cur;
            }
        }

        //被围绕的区域
        class Solution2 {
            int m, n;
            int[] dx = {0, 0, 1, -1};
            int[] dy = {1, -1, 0, 0};

            public void solve(char[][] board) {
                if (board == null || board.length == 0) return;
                m = board.length;
                n = board[0].length;

                // 1. 从四条边出发，标记所有连通的 'O' 为 'A'
                // 上下两条边
                for (int j = 0; j < n; j++) {
                    if (board[0][j] == 'O') dfs(board, 0, j);
                    if (board[m - 1][j] == 'O') dfs(board, m - 1, j);
                }
                // 左右两条边（跳过角落避免重复）
                for (int i = 1; i < m - 1; i++) {
                    if (board[i][0] == 'O') dfs(board, i, 0);
                    if (board[i][n - 1] == 'O') dfs(board, i, n - 1);
                }

                // 2. 遍历矩阵，'O' 改为 'X'，'A' 还原为 'O'
                for (int i = 0; i < m; i++) {
                    for (int j = 0; j < n; j++) {
                        if (board[i][j] == 'O') {
                            board[i][j] = 'X';      // 被围绕的区域
                        } else if (board[i][j] == 'A') {
                            board[i][j] = 'O';      // 边界连通区域
                        }
                    }
                }
            }

            // DFS：把从 (x, y) 出发连通的 'O' 标记为 'A'
            private void dfs(char[][] board, int x, int y) {
                board[x][y] = 'A';  // 立即标记

                for (int k = 0; k < 4; k++) {
                    int nx = x + dx[k];
                    int ny = y + dy[k];
                    if (nx >= 0 && nx < m && ny >= 0 && ny < n && board[nx][ny] == 'O') {
                        dfs(board, nx, ny);
                    }
                }
            }
        }
    }
}